
package com.algorithm.code.string;

import java.util.Arrays;
import java.util.Objects;

/**
 * KMP
 * 参考：https://github.com/mission-peace/interview/blob/master/src/com/interview/string/SubstringSearch.java
 */
public class KMP {

    public static void main(String[] args) {
        KMP kmp = new KMP();
        String str = "abcxabcdabcdabcy";
        String subString = "abcdabcy";

        int index = kmp.find(str, subString);

        System.out.println(index);
    }

    /**
     * 
     * @param str         : 主串
     * @param pattern：模式串
     * @return 模式串在主串中的起始位置
     */
    public final int find(final String str, final String pattern) {

        if (Objects.isNull(str) || Objects.isNull(pattern)) {
            return -1;
        }

        int[] nextArray = this.getNextArray(pattern);

        int i = 0, j = 0;
        while (i < str.length() && j < pattern.length()) {

            if (str.charAt(i) == pattern.charAt(j)) {
                ++i;
                ++j;
            } else {
                // 向前移动模式串位置，至相应位置
                if (j != 0) {
                    j = nextArray[j - 1];
                } else {
                    // 移动主串位置，因为模式串到头了
                    ++i;
                }
            }

        }

        if (j == pattern.length()) {
            return i - j;
        }

        return -1;
    }

    /**
     * 根据模式串生成模式串查找数组 主要是查找模式子串的前缀子串和后缀子串的匹配情况
     * 
     * @return
     */
    private final int[] getNextArray(final String pattern) {

        /**
         * next数组
         */
        int[] nextArray = new int[pattern.length()];
        Arrays.fill(nextArray, 0);
        int index = 0;
        /**
         * 模式串指针从1开始
         */
        int i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(index)) {
                nextArray[i] = index + 1;
                i++;
                index++;
            } else {
                /**
                 * 如果不相等继续向前找 1. index ！= 0，说明数组中还有值；如果还不相等则继续向前找 2. index = 0，
                 * 说明数组中没值了；pattern到头了。只能移动主串的位置了。
                 */
                if (index != 0) {
                    index = nextArray[index - 1];
                } else {
                    nextArray[i] = 0;
                    ++i;
                }
            }
        }
        return nextArray;
    }
}